Möbius Inversion

Introduction

Many important arithmetic functions are defined using sums over divisors.
Möbius inversion is a technique that lets you reverse such sums.
It answers questions of the form:
- If I know the sum of $f(d)$ over all divisors $d$ of $n$, can I recover $f(n)$ itself?
This article builds intuition step by step:
- What divisor sums look like
- The Möbius function
- A new way to combine arithmetic functions
- The inversion formula
- Applications and examples

Sums Over Divisors: The Basic Landscape

Many classical functions are defined using divisor sums:
- $\sigma(n)$ = sum of all positive divisors of $n$
- $\tau(n)$ = number of positive divisors of $n$
- $\varphi(n)$ = Euler’s totient function, which satisfies $$\sum_{d\mid n} \varphi(d) = n$$
General pattern:
- Suppose $g(n)$ is defined by $$g(n) = \sum_{d\mid n} f(d).$$
- Möbius inversion tells us how to recover $f(n)$ from $g(n)$.

The Möbius Function $\mu(n)$: Definition and First Properties

The Möbius function is denoted by the Greek letter $\mu$, pronounced "mu"
It is defined for positive integers $n$:
- $\mu(1) = 1$
- $\mu(n) = 0$ if $n$ has any repeated prime factor
  - (i.e., $n$ is not squarefree)
- $\mu(n) = (-1)^k$ if $n$ is a product of $k$ distinct primes
Examples:
- $\mu(6) = \mu(2\cdot 3) = (+1)$
- $\mu(12) = 0$ (because $12$ has $2^2$)
- $\mu(30) = \mu(2\cdot 3\cdot 5) = (-1)^3 = -1$
Key idea:
- $\mu(n)$ acts like a “correction factor” that cancels out divisor sums.

Understanding Multiplicative Functions Through Examples

A function $f$ is multiplicative if:
- $f(1)=1$
- $f(ab)=f(a)f(b)$ whenever $\gcd(a,b)=1$
Examples:
- $\mu(n)$ is multiplicative
- $\varphi(n)$ is multiplicative
- $\tau(n)$ and $\sigma(n)$ are multiplicative
Why this matters:
- Multiplicativity makes divisor sums easier to understand
- Many inversion formulas behave nicely with multiplicative functions

Dirichlet Convolution: A Natural Way to Combine Arithmetic Functions

Given two arithmetic functions $f$ and $g$, their Dirichlet convolution is: $$(f * g)(n) = \sum_{d\mid n} f(d)\,g(n/d).$$
Think of it as a “divisor‑sum version” of convolution.
Important facts:
- Convolution is commutative and associative
- The identity element is the function $\varepsilon(n)$ defined by
  - $\varepsilon(1)=1$, $\varepsilon(n)=0$ for $n>1$
  - $\varepsilon$ is the Greek letter epsilon
- The constant function $1(n)=1$ for all $n$ satisfies $$1 * \mu = \varepsilon.$$

This last identity is the heart of Möbius inversion.

The Möbius Inversion Formula: Statement and Intuition

Statement

If $$g(n) = \sum_{d\mid n} f(d),$$ then $$f(n) = \sum_{d\mid n} \mu(d)\, g(n/d).$$

Intuition

Think of $g$ as a “blurred” version of $f$ created by adding up values over divisors.
The Möbius function provides the exact correction needed to “un‑blur” $g$.
The formula works because $\mu$ is the inverse of the constant function $1$ under convolution.

Why Möbius Inversion Works: A Gentle Proof

Start with the identity $$1 * \mu = \varepsilon.$$
If $g = 1 * f$, then convolving both sides with $\mu$ gives: $$g * \mu = (1 * f) * \mu = f * (1 * \mu) = f * \varepsilon = f.$$
Expanding $g * \mu$ gives the inversion formula: $$f(n) = \sum_{d\mid n} \mu(d)\, g(n/d).$$
The proof is short because the convolution viewpoint makes the structure transparent.

Common Patterns: When to Use Möbius Inversion

Use Möbius inversion when:

You know a formula involving $\sum_{d\mid n} f(d)$ and want $f(n)$
You have a divisor‑sum identity and want to “undo” it
You see a pattern like:
- “$g$ counts something in all multiples/divisors of $n$”
- “$g$ is an accumulated version of $f$”
You want to express a function in terms of another that is easier to compute

Classic Applications

Counting Squarefree Numbers

The indicator of squarefree numbers is: $$\sum_{d^2 \mid n} \mu(d).$$
Möbius inversion helps isolate contributions from square factors.

Recovering a Function from Its Divisor Sum

If $g(n)=\sum_{d\mid n} f(d)$, then $$f(n)=\sum_{d\mid n} \mu(d)\,g(n/d).$$

The Euler Totient Function Revisited

The identity $$\sum_{d\mid n} \varphi(d) = n$$ implies $$\varphi(n) = \sum_{d\mid n} \mu(d)\,(n/d).$$

Advanced but Accessible Examples

Inverting Summatory Functions

Suppose $G(n)=\sum_{d\mid n} f(d)$ is easier to compute than $f(n)$.
Möbius inversion gives a direct formula for $f(n)$.

Detecting Coprimality

The identity $$\sum_{d\mid \gcd(m,n)} \mu(d) = \begin{cases} 1 & \text{if }\gcd(m,n)=1,\\ 0 & \text{otherwise} \end{cases}$$ shows how $\mu$ can act as a “coprimality detector.”

Connections to Generating Functions and Dirichlet Series

Dirichlet series turn convolution into multiplication: $$\sum_{n\ge1} \frac{(f*g)(n)}{n^s} = \left(\sum_{n\ge1} \frac{f(n)}{n^s}\right) \left(\sum_{n\ge1} \frac{g(n)}{n^s}\right).$$
The series for $\mu$ is the reciprocal of the Riemann zeta function: $$\sum_{n\ge1} \frac{\mu(n)}{n^s} = \frac{1}{\zeta(s)}.$$
This viewpoint explains why $\mu$ acts as an inverse to the constant function $1$.

Summary and Key Takeaways

Möbius inversion is a method for reversing divisor sums.
The Möbius function $\mu(n)$ is the key ingredient.
Dirichlet convolution provides the right algebraic framework.
Many classical identities (like those involving $\varphi(n)$) are special cases.
The technique is powerful but relies on simple ideas.

Exercises

Try these to solidify your understanding:

Compute $\mu(n)$ for the following values:
- $n=1, 8, 10, 18, 30, 45$.
Solution
Task: Compute $\mu(n)$ for $n=1, 8, 10, 18, 30, 45$.
- Recall:
  - $\mu(1)=1$
  - $\mu(n)=0$ if $n$ has a squared prime factor
  - $\mu(n)=(-1)^k$ if $n$ is a product of $k$ distinct primes
- $n=1$
  - By definition, $\mu(1)=1$.
- $n=8$
  - $8=2^3$ has a repeated prime factor ($2^2$ divides $8$).
  - So $\mu(8)=0$.
- $n=10$
  - $10=2\cdot 5$ (two distinct primes).
  - So $\mu(10)=(-1)^2=1$.
- $n=18$
  - $18=2\cdot 3^2$ has a repeated prime factor ($3^2$).
  - So $\mu(18)=0$.
- $n=30$
  - $30=2\cdot 3\cdot 5$ (three distinct primes).
  - So $\mu(30)=(-1)^3=-1$.
- $n=45$
  - $45=3^2\cdot 5$ has a repeated prime factor ($3^2$).
  - So $\mu(45)=0$.
Verify the identity $$\sum_{d\mid n} \mu(d) = \begin{cases} 1 & n=1,\\ 0 & n>1. \end{cases}$$ by checking it for $n=1$ through $n=12$.
Solution
Task: Verify $$\sum_{d\mid n} \mu(d)= \begin{cases} 1 & n=1,\\ 0 & n>1 \end{cases}$$ for $n=1,\dots,12$.
We list divisors and sum $\mu(d)$.
- $n=1$
  - Divisors: $1$
  - Sum: $\mu(1)=1$.
- $n=2$
  - Divisors: $1,2$
  - $\mu(1)=1,\ \mu(2)=-1$
  - Sum: $1+(-1)=0$.
- $n=3$
  - Divisors: $1,3$
  - $\mu(1)=1,\ \mu(3)=-1$
  - Sum: $1+(-1)=0$.
- $n=4$
  - Divisors: $1,2,4$
  - $\mu(1)=1,\ \mu(2)=-1,\ \mu(4)=0$ (since $4=2^2$)
  - Sum: $1-1+0=0$.
- $n=5$
  - Divisors: $1,5$
  - $\mu(1)=1,\ \mu(5)=-1$
  - Sum: $1-1=0$.
- $n=6$
  - Divisors: $1,2,3,6$
  - $\mu(1)=1,\ \mu(2)=-1,\ \mu(3)=-1,\ \mu(6)=1$
  - Sum: $1-1-1+1=0$.
- $n=7$
  - Divisors: $1,7$
  - $\mu(1)=1,\ \mu(7)=-1$
  - Sum: $1-1=0$.
- $n=8$
  - Divisors: $1,2,4,8$
  - $\mu(1)=1,\ \mu(2)=-1,\ \mu(4)=0,\ \mu(8)=0$
  - Sum: $1-1+0+0=0$.
- $n=9$
  - Divisors: $1,3,9$
  - $\mu(1)=1,\ \mu(3)=-1,\ \mu(9)=0$
  - Sum: $1-1+0=0$.
- $n=10$
  - Divisors: $1,2,5,10$
  - $\mu(1)=1,\ \mu(2)=-1,\ \mu(5)=-1,\ \mu(10)=1$
  - Sum: $1-1-1+1=0$.
- $n=11$
  - Divisors: $1,11$
  - $\mu(1)=1,\ \mu(11)=-1$
  - Sum: $1-1=0$.
- $n=12$
  - Divisors: $1,2,3,4,6,12$
  - $\mu(1)=1,\ \mu(2)=-1,\ \mu(3)=-1,\ \mu(4)=0,\ \mu(6)=1,\ \mu(12)=0$
  - Sum: $1-1-1+0+1+0=0$.
Conclusion: The identity holds for $1\le n\le 12$, and in fact for all $n$.
Suppose $g(n)=\sum_{d\mid n} f(d)$ and you are told that $g(n)=n$.
- Use Möbius inversion to find $f(n)$ explicitly.
Solution
Task: If $g(n)=\sum_{d\mid n} f(d)$ and $g(n)=n$, find $f(n)$.
- We are in the standard Möbius inversion setup: $$g(n)=\sum_{d\mid n} f(d).$$
- Möbius inversion says: $$f(n)=\sum_{d\mid n} \mu(d)\, g(n/d).$$
- Here $g(n/d)=n/d$, so $$f(n)=\sum_{d\mid n} \mu(d)\,\frac{n}{d} = n\sum_{d\mid n} \frac{\mu(d)}{d}.$$
This expression is already a valid closed form. But we can recognize it:
- Compare with the known identity $$\varphi(n)=\sum_{d\mid n} \mu(d)\,\frac{n}{d}.$$
- Therefore $$f(n)=\varphi(n).$$
Answer: $f(n)=\varphi(n)$, Euler’s totient function.
Let $h(n)=\sum_{d\mid n} d$.
- Use Möbius inversion to express $n$ in terms of $h$ and $\mu$.
Solution
Task: Let $h(n)=\sum_{d\mid n} d$. Express $n$ in terms of $h$ and $\mu$.
- We have $$h(n)=\sum_{d\mid n} d.$$
- Notice that $h$ is the divisor sum of the function $f(d)=d$: $$h(n)=\sum_{d\mid n} f(d),\quad f(d)=d.$$
- By Möbius inversion, $$f(n)=\sum_{d\mid n} \mu(d)\, h(n/d).$$
- But $f(n)=n$, so $$n=\sum_{d\mid n} \mu(d)\, h(n/d).$$
Answer: $$n=\sum_{d\mid n} \mu(d)\, h(n/d).$$
Show that $$\varphi(n)=\sum_{d\mid n} \mu(d)\,(n/d).$$
- Then compute $\varphi(12)$ using this formula.
Solution
Task: Show $$\varphi(n)=\sum_{d\mid n} \mu(d)\,(n/d),$$ then compute $\varphi(12)$ using this formula.
Step 1: Derive the formula
- We know the classical identity: $$\sum_{d\mid n} \varphi(d)=n.$$
- This can be written as $$n = \sum_{d\mid n} \varphi(d).$$
- Compare with the general pattern $g(n)=\sum_{d\mid n} f(d)$:
  - Here $g(n)=n$ and $f(d)=\varphi(d)$.
- By Möbius inversion, $$\varphi(n)=\sum_{d\mid n} \mu(d)\, g(n/d) =\sum_{d\mid n} \mu(d)\,\frac{n}{d}.$$
Step 2: Compute $\varphi(12)$
- Divisors of $12$: $1,2,3,4,6,12$.
- We need $\mu(d)$ and $12/d$:
  - $d=1$: $\mu(1)=1$, $12/1=12$ → contribution $1\cdot 12=12$
  - $d=2$: $\mu(2)=-1$, $12/2=6$ → contribution $-1\cdot 6=-6$
  - $d=3$: $\mu(3)=-1$, $12/3=4$ → contribution $-1\cdot 4=-4$
  - $d=4$: $\mu(4)=0$ → contribution $0$
  - $d=6$: $\mu(6)=1$, $12/6=2$ → contribution $1\cdot 2=2$
  - $d=12$: $\mu(12)=0$ → contribution $0$
- Sum: $$\varphi(12)=12-6-4+0+2+0=4.$$
Answer:
- Formula: $\displaystyle \varphi(n)=\sum_{d\mid n} \mu(d)\,\frac{n}{d}$.
- Value: $\varphi(12)=4$.
(A bit more challenging) Prove that $$\sum_{d\mid \gcd(m,n)} \mu(d)$$ is $1$ if $\gcd(m,n)=1$ and $0$ otherwise.
Solution
Task: Prove that $$\sum_{d\mid \gcd(m,n)} \mu(d)= \begin{cases} 1 & \gcd(m,n)=1,\\ 0 & \gcd(m,n)>1. \end{cases}$$ Let $g=\gcd(m,n)$.
- The sum is $$\sum_{d\mid g} \mu(d).$$
- From Exercise 2 (and the general identity), we know: $$\sum_{d\mid k} \mu(d)= \begin{cases} 1 & k=1,\\ 0 & k>1. \end{cases}$$
- Apply this with $k=g$:
  - If $g=1$ (i.e. $\gcd(m,n)=1$), the sum is $1$.
  - If $g>1$ (i.e. $\gcd(m,n)>1$), the sum is $0$.
Answer: The sum over divisors of $\gcd(m,n)$ of $\mu(d)$ is $1$ when $m,n$ are coprime and $0$ otherwise.
Let $f(n)=1$ for all $n$.
- Compute $g(n)=\sum_{d\mid n} f(d)$
- Then invert to recover $f(n)$ using Möbius inversion.
Solution
Task: Let $f(n)=1$ for all $n$. Compute $g(n)=\sum_{d\mid n} f(d)$, then invert to recover $f(n)$.
Step 1: Compute $g(n)$
- Since $f(d)=1$ for every $d$, $$g(n)=\sum_{d\mid n} f(d)=\sum_{d\mid n} 1.$$
- This is just the number of divisors of $n$, usually denoted $\tau(n)$.
- So $g(n)=\tau(n)$.
Step 2: Invert using Möbius inversion
- We have $$g(n)=\sum_{d\mid n} f(d),$$ with $g(n)=\tau(n)$ and $f(n)=1$.
- Möbius inversion gives $$f(n)=\sum_{d\mid n} \mu(d)\, g(n/d) =\sum_{d\mid n} \mu(d)\,\tau(n/d).$$
- But we know $f(n)=1$, so this identity becomes $$1=\sum_{d\mid n} \mu(d)\,\tau(n/d)$$ for every $n$.
Answer:
- $g(n)=\tau(n)$, the number of divisors of $n$.
- Möbius inversion recovers $f(n)=1$ via $$1=\sum_{d\mid n} \mu(d)\,\tau(n/d).$$